// 题目描述
// 19. 删除链表的倒数第 N 个结点
// 难度
// 中等
// 2627
// 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
//   示例 1：
// 输入：head = [1,2,3,4,5], n = 2
// 输出：[1,2,3,5]
// 示例 2：
// 输入：head = [1], n = 1
// 输出：[]
// 示例 3：
// 输入：head = [1,2], n = 1
// 输出：[1]
//   提示：
// 链表中结点的数目为 sz
// 1 <= sz <= 30
// 0 <= Node.val <= 100
// 1 <= n <= sz
//   进阶：你能尝试使用一趟扫描实现吗？
// 通过次数1,183,197提交次数2,580,531

function ListNode(val, next) {
  this.val = (val === undefined ? 0 : val)
  this.next = (next === undefined ? null : next)
}

/**
 * 寻找链表的倒数第 n 个节点
 * @param head
 * @param n
 * @returns {*}
 */
function findFromEnd(head, n) {
  let p1 = head
  for (let i = 0; i < n; i++) {
    p1 = p1.next
  }

  let p2 = head
  while (p1 !== null) {
    p2 = p2.next
    p1 = p1.next
  }

  return p2
}

/**
 * @param {ListNode} head
 * @param {number} n
 * @return {ListNode}
 */
var removeNthFromEnd = function (head, n) {
  let dummy = new ListNode('#')
  dummy.next = head

  let pre = findFromEnd(dummy, n + 1)
  pre.next = pre.next.next

  return dummy.next
}

const lst = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5)))))
const lst2 = removeNthFromEnd(lst, 2)
console.log(lst2)






















